Amortized Cost

释义 Definition

摊还成本 / 均摊代价：在一系列操作中，把某些“偶尔很贵”的操作成本分摊到多次操作上后得到的平均每次成本。常用于算法与数据结构分析，说明长期平均性能可能很好，即使个别操作很慢。（不同于概率意义上的“平均情况”，而是对固定操作序列的总体分摊。）

发音 Pronunciation

/əˈmɔːrtaɪzd kɔːst/

例句 Examples

Pushing an item onto a dynamic array has an amortized cost of O(1).
向动态数组末尾添加一个元素的摊还成本是 O(1)。

Although resizing occasionally takes O(n) time, the amortized cost per insertion remains constant over many operations.
尽管扩容偶尔需要 O(n) 时间，但在大量操作中，每次插入的摊还成本仍然保持为常数。

词源 Etymology

amortized 来自动词 amortize，源于法语 amortir（“减弱、消除、使失去作用”），词根与 mort（“死亡”）相关，原意有“使其消失/逐渐消去”的感觉；在金融语境中引申为“把一次性成本分期摊销”。在计算机科学中进一步借用为“把少数昂贵操作的代价分摊到整体操作序列中”，因此形成术语 amortized cost。

相关词 Related Words

• Amortized Analysis
• Average-Case
• Worst-Case
• Time Complexity
• Potential Method
• Aggregate Method
• Accounting Method
• Dynamic Array
• Data Structure

文学与著作中的用例 Literary Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein，《算法导论》）：在动态表（dynamic table）扩容等主题中系统使用并解释 amortized cost。
• Data Structures and Algorithm Analysis（Mark Allen Weiss）：在栈/队列、动态数组等章节讨论均摊分析与 amortized cost。
• Algorithms（Robert Sedgewick & Kevin Wayne）：在相关数据结构与性能分析语境中使用均摊思想并出现该术语。